คณิตศาสตร์เชิงการตัดสินใจ: โครงสร้างของเครือข่ายการขนส่ง

เครือข่ายการขนส่งเป็นโครงสร้างทางคณิตศาสตร์เฉพาะที่ใช้จำลองการเคลื่อนย้ายสินค้า ข้อมูล หรือวัสดุผ่านระบบช่องทางที่มีข้อจำกัด โดยเปลี่ยนกราฟทิศทางปกติให้กลายเป็นกรอบการทำงานที่มีจุดเริ่มต้นและจุดสิ้นสุดที่กำหนดไว้ พร้อมกับกำหนดข้อจำกัดด้านกายภาพ (จุดอุดตัน) บนทุกการเชื่อมต่อภายในระบบ

นิยามของเครือข่ายการขนส่ง

ตาม นิยาม 10.1.1, เครือข่ายการขนส่ง (หรือเพียงแค่เครือข่าย) เป็นกราฟทิศทางที่มีน้ำหนักและง่ายซึ่งต้องปฏิบัติตามเกณฑ์หลักสามประการ:

คุณสมบัติ (ก): แหล่งกำเนิด

จุดยอดที่กำหนดไว้ ซึ่งคือ แหล่งกำเนิด ($a$ หรือ $s$) แทนจุดเริ่มต้น มีเส้นเชื่อมเข้ามาไม่ได้ (ดีกรีเข้า = 0) และทำหน้าที่เป็นแหล่งจัดหาที่ไม่มีที่สิ้นสุด

คุณสมบัติ (ข): ปลายทาง

จุดยอดที่กำหนดไว้ ซึ่งคือ ปลายทาง ($z$ หรือ $t$) แทนผู้บริโภคสุดท้าย มีเส้นเชื่อมออกไม่ได้ (ดีกรีออก = 0)

คุณสมบัติ (ค): ความจุ

น้ำหนัก $C_{ij}$ ของแต่ละเส้นเชื่อมทิศทาง $(i, j)$ เรียกว่า ความจุ. ต้องเป็นจำนวนบวกหรือศูนย์ ($C_{ij} \geq 0$) ซึ่งแสดงถึงปริมาณการไหลสูงสุดที่เส้นเชื่อมสามารถรองรับได้

แบบจำลองจากโลกความเป็นจริง: ระบบไฟฟ้าระดับภูมิภาค

เพื่อให้แนวคิดที่เป็นนามธรรมเหล่านี้มีชีวิตชีวา ลองพิจารณาเครือข่ายไฟฟ้าในภูมิภาค:

แหล่งกำเนิด: เขื่อนขนาดใหญ่ที่ผลิตพลังงานไฟฟ้า ไม่มีกระแสไฟฟ้าใดๆ เข้ามาในเขื่อนจากเครือข่ายไฟฟ้าเอง
ปลายทาง: เขตอุตสาหกรรมหนัก ใช้พลังงานไฟฟ้าทั้งหมดที่เข้ามาเพื่อขับเครื่องจักร ไม่มีพลังงานใดกลับคืนสู่เครือข่าย
เส้นเชื่อมและค่าความจุ: สายส่งไฟฟ้าคือเส้นเชื่อม ความจุของมันคือค่าแอมแปร์สูงสุดที่สายไฟฟ้าสามารถรองรับได้โดยไม่ล้มเหลวจากความร้อน
จุดกลาง: Local substations that redirect the flow without "consuming" it (Conservation of Flow).

Capacity vs. Flow Nuance

It is critical to distinguish between Capacity and Flow. The capacity $C_{ij}$ is a static physical property—it is the potential volume. The flow $F_{ij}$ is the actual volume being moved at a specific moment. On this slide, we focus exclusively on the architectural limits (capacities) rather than the current state of movement.

🎯 Core Principle: Structural Constraints

Every transport network is a directed graph where flow moves from a supplier (Source) to a consumer (Sink) through conduits limited by non-negative capacities.

Source: $deg^-(a) = 0 \quad | \quad$ Sink: $deg^+(z) = 0 \quad | \quad \text{Capacity}: C_{ij} \geq 0

QUESTION 1

What are the three mandatory components of a transport network according to Definition 10.1.1?

Directed graph, unique source/sink, and non-negative capacities.

Undirected graph, infinite sources, and negative weights.

Weighted graph, bipartite matching, and equal in-degrees.

Simple graph, source with in-degree 1, and zero capacity edges.

QUESTION 2

What is the primary difference between Capacity ($C_{ij}$) and Flow ($F_{ij}$)?

Capacity is the maximum limit; Flow is the actual amount currently moving.

Capacity is dynamic; Flow is a static physical property.

Capacity only applies to the sink; Flow only applies to the source.

There is no difference; they are interchangeable terms in network theory.

QUESTION 3

In the context of a power grid model, what would represent the Source?

A power generation plant like a hydroelectric dam.

A residential neighborhood consuming electricity.

An intermediate substation redirecting power.

The physical copper wires used for transmission.

QUESTION 4

State the condition for a vertex $z$ to be considered a Sink.

It must have an out-degree of zero ($deg^+(z) = 0$).

It must have an in-degree of zero ($deg^-(z) = 0$).

The sum of its capacities must be infinite.

It must be connected to every other node in the graph.

QUESTION 5

[🧩 SYSTEM_FORCED] What is a network? (Focus on Definition 10.1.1 criteria).

A simple, weighted, directed graph with a designated source (no incoming edges), a designated sink (no outgoing edges), and non-negative capacities on all edges.

A bipartite graph where every node has a matching edge.

Any graph that contains a path from node a to node z.

A directed graph where the number of edges equals the number of vertices.